package puzzle.projecteuler.p200;

import astudy.util.AdvMath;

public class Problem179C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int m = 10000000;
		int[] a = d(m);
		int c = 0;
		for (int n = 2; n < m; n ++) {
			if (a[n] == a[n+1]) c ++;
		}
		System.out.println(c);
	}
	
	/**
	 * 采用类似筛法的方式，计算所有n(<m)对应的因子数目d(n)
	 * @param m
	 * @return
	 */
	public static int[] d(Integer m) {
		
		int sqrt_m = (int)Math.sqrt(m)+1;
		Integer[] primes = AdvMath.primes(sqrt_m);
		
		int[] tmp = new int[m+1];
		int[] res = new int[m+1];
		for (int i = 0; i < tmp.length; i ++) {
			tmp[i] = i;
			res[i] = 1;
		}
		
		tmp[0] = -1;
		res[0] = -1;
		tmp[1] = 1;
		res[1] = 1;
		
		for (int i = 0; i < primes.length; i ++) {
			int p = primes[i];
			for (int j = p; j <= m; j += p) {
				int c = 0;
				while (tmp[j]%p == 0) {
					tmp[j] /= p;
					c ++;
				}
				res[j] *= c+1;
			}
		}
		for (int i = 1; i < tmp.length; i ++) {
			if (tmp[i] != 1) {
				res[i] *= 2; 
			}
		}

		return res;
	}
}
